Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/t3_1/doc.lha/documentation/manual/evaluator.mss

Text File | 1987-06-30 | 10.6 KB | 280 lines

@part[EVALUATOR, root "TMAN.MSS"]       @comment{ -*-Mode:T;System:TMAN-*-}
@appendix[A meta-circular evaluator]
@label[EvaluatorAppendix]               @comment{ semantics chapter }

This appendix gives an annotated listing of an evaluator for @Tau[].
This evaluator is written in @Tau[] (thus the adjective
@qu"meta-circular," since it employs the notation it tries to
describe) and attempts to continue in the spirit of @cite[STEELE78ART]
and @cite[MCCARTHY60].  It represents an attempt, short of writing a
denotational semantics, to provide a moderately precise description of
@Tau[]'s semantics.
@index[Evaluation]

This interpreter should also be of some interest simply as an extended
example of a program written in @Tau[].

It is important to know what this evaluator is not:
@begin[itemize]
It is not efficient.  It expressly makes no effort at all to do things in
clever or efficient ways.

It is not complete.  It tries to define most of the special forms that
it uses, but does not define any primitive procedures such as @tc[CAR]
or @tc[APPLY].  However, any special forms that have been omitted are,
for the most part, trivially definable in terms of the special forms
here defined, as source-to-source transformations; in fact this is the
how the existing implementation works.

It is not parameterized (that is, extensible).  No means of passing in
syntax tables or adding syntactic extensions (@tc[DEFINE-SYNTAX])
is provided.

It makes no attempt to detect or deal with error conditions, such as
unevaluable expressions, unbound variables, or wrong number of arguments
in calls.
@end[itemize]

@begin[group]
@tc[EVALUATE], the universal function, computes the value of an
expression in a given variable environment.  It dispatches to
a specialist routine on the basis of the syntax of the expression.

@begin[TEG]
(DEFINE (EVALUATE EXP ENV)
  (COND ((SYMBOL? EXP)
         (VALUE EXP ENV))
        ((OR (NUMBER? EXP)
             (CHARACTER? EXP)
             (STRING? EXP))
         EXP)
        ((PAIR? EXP)
         (CASE (CAR EXP)
           ((QUOTE)    (EVALUATE-QUOTE    EXP ENV))
           ((IF)       (EVALUATE-IF       EXP ENV))
           ((BLOCK)    (EVALUATE-BLOCK    EXP ENV))
           ((LAMBDA)   (EVALUATE-LAMBDA   EXP ENV))
           ((DEFINE)   (EVALUATE-DEFINE   EXP ENV))
           ((LSET)     (EVALUATE-LSET     EXP ENV))
           ((SET)      (EVALUATE-SET      EXP ENV))
           ((OBJECT)   (EVALUATE-OBJECT   EXP ENV))
           ((LOCALE)   (EVALUATE-LOCALE   EXP ENV))
           ((LOCATIVE) (EVALUATE-LOCATIVE EXP ENV))
           ((COND)     (EVALUATE-COND     EXP ENV))
           ((AND)      (EVALUATE-AND      EXP ENV))
           ((OR)       (EVALUATE-OR       EXP ENV))
           ((LET)      (EVALUATE-LET      EXP ENV))
           (ELSE       (EVALUATE-CALL     EXP ENV))))))
@end[TEG]
@end[group]

@tc[EVALUATE-CALL] computes the value of a call to a procedure.
The procedure and arguments are evaluated recursively, and the procedure
is invoked using @tc[APPLY] (assumed to be primitive; not defined by this
Appendix).

@begin[TEG]
(DEFINE (EVALUATE-CALL EXP ENV)
  (APPLY (EVALUATE (CAR EXP) ENV)
         (MAP (LAMBDA (ARG) (EVALUATE ARG ENV))
              (CDR EXP))))
@end[TEG]

@tc[QUOTE], @tc[IF], and @tc[BLOCK] have straightforward definitions.

@begin[TEG]
(DEFINE (EVALUATE-QUOTE EXP ENV)
  (CADR EXP))

(DEFINE (EVALUATE-IF EXP ENV)
  (IF (EVALUATE (CADR EXP) ENV)
      (EVALUATE (CADDR EXP) ENV)
      (EVALUATE (CADDDR EXP) ENV)))

(DEFINE (EVALUATE-BLOCK EXP ENV)
  (EVALUATE-SEQUENCE (CDR EXP) ENV))
@end[TEG]

@tc[EVALUATE-SEQUENCE] is an auxiliary routine called in several places.
It needs to be careful to maintain tail-recursive semantics; thus the
loop termination when @wt[(NULL? (CDR EXPS))] instead of the more
obvious @wt[(NULL? EXPS)].

@begin[TEG]
(DEFINE (EVALUATE-SEQUENCE EXPS ENV)
  (COND ((NULL? (CDR EXPS))
         (EVALUATE (CAR EXPS) ENV))
        (ELSE
         (EVALUATE (CAR EXPS) ENV)
         (EVALUATE-SEQUENCE (CDR EXPS) ENV))))
@end[TEG]

Surprisingly, @tc[EVALUATE-LAMBDA] has a very straightforward definition
in terms of @tc[LAMBDA]: it simply returns a procedure which evaluates
the body of the lambda-expression in an appropriately augmented variable
environment.

@begin[TEG]
(DEFINE (EVALUATE-LAMBDA EXP ENV)
  (LAMBDA ARGS
    (EVALUATE-SEQUENCE (CDDR EXP)
                       (BIND-VARIABLES (CADR EXP) ARGS ENV))))
@end[TEG]

@tc[SET] has two cases; whereas assignment to a variable must be
primitive, assignment to a generalized @qu"place" is performed using a
simple source-code rewrite.

@begin[TEG]
(DEFINE (EVALUATE-SET EXP ENV)
  (LET ((PLACE (CADR EXP)))
    (COND ((ATOM? PLACE)
           (SET-VALUE PLACE ENV (EVALUATE (CADDR EXP) ENV) NIL))
          (ELSE
           (EVALUATE `((SETTER ,(CAR PLACE)) ,@@(CDR PLACE) ,(CADDR EXP))
                     ENV)))))
@end[TEG]

@wt[(SET @i[variable value])] and @wt[(LSET @i[variable value])] are
interpreted in exactly the same way, except for the fourth argument
passed to @tc[SET-VALUE], which is a flag to be eventually passed to
@tc[ENV-LOOKUP]; this determines whether the lookup proceeds outwards
past the innermost locale, or stops there, where the variable is either
replaced or inserted in the environment.  @tc[DEFINE] is the same as
@tc[LSET], but permits extended syntax for defining procedures.

@begin[TEG]
(DEFINE (EVALUATE-LSET EXP ENV)
  (SET-VALUE (CADR EXP) ENV (EVALUATE (CADDR EXP) ENV) T))

(DEFINE (EVALUATE-DEFINE EXP ENV)
  (LET ((PATTERN (CADR EXP)))
    (COND ((ATOM? PATTERN)
           (EVALUATE-LSET EXP ENV))
          (ELSE
           (EVALUATE-LSET `(LSET ,(CAR PATTERN)
                                 (LAMBDA ,(CDR PATTERN) ,@@(CDDR EXP)))
                          ENV)))))
@end[TEG]

The evaluator implements @tc[OBJECT] using @tc[JOIN] by
iteratively constructing, one method-clause at a time, an object which
will have the requisite behavior.
The auxiliary routine @tc[EVALUATE-OBJECT-AUX] could have been defined
using @tc[LABELS], but the code would have become too deeply indented,
exacerbating this manual's already forbidding formatting problems.

@begin[TEG]
(DEFINE (EVALUATE-OBJECT EXP ENV)
  (EVALUATE-OBJECT-AUX (EVALUATE (CADR EXP) ENV) (CDDR EXP) ENV))

(DEFINE (EVALUATE-OBJECT-AUX PROC CLAUSES ENV)
  (COND ((NULL? CLAUSES)
         (OBJECT PROC))
        (ELSE
         (LET ((CLAUSE (CAR CLAUSES)))
           (JOIN (OBJECT PROC
                         (((EVALUATE (CAAR CLAUSE) ENV) SELF . ARGS)
                          (EVALUATE-SEQUENCE (CDR CLAUSE)
                                             (BIND-VARIABLES (CDAR CLAUSE)
                                                             (CONS SELF ARGS)
                                                             ENV))))
                 (EVALUATE-OBJECT-AUX NIL (CDR CLAUSES) ENV))))))
@end[TEG]

As described elsewhere in this manual, a locale is an environment whose
list of bound variables can be mutated, in a controlled way, as a
side-effect.@index[locales]  To accomplish this, @tc[LOCALE] is
implemented using a local variable @tc[THE-ENV] which is assigned new
values (using a @tc[SET] side-effect) as new variables are added to the
environment.  This happens whenever a locative for a variable is needed
and cannot be located, either because the enclosing environment has no
binding for the variable or because the @tc[LOCAL?] argument to
@tc[ENV-LOOKUP] is true and the lookup must stop at the level of the
locale.

The actual locale object has a trivial definition for the
@tc[ENV-LOOKUP] method which jumps directly to whatever the current
value of @tc[THE-ENV] happens to be.

@begin[TEG]
(DEFINE (EVALUATE-LOCALE EXP ENV)
  (LET ((THE-ENV NIL))
    (SET THE-ENV
         (OBJECT NIL
                 ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
                  (COND ((AND LOCAL? (NOT CREATE?))
                         NIL)
                        ((AND (NOT LOCAL?)
                              (ENV-LOOKUP ENV ID NIL NIL)))
                        (CREATE?
                         (SET THE-ENV
                              (BIND-VARIABLE ID (UNDEFINED-VALUE) THE-ENV))
                         (ENV-LOOKUP THE-ENV ID LOCAL? CREATE?))
                        (ELSE NIL)))))
    (LET ((THE-LOCALE
           (OBJECT NIL
                   ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
                    (ENV-LOOKUP THE-ENV ID LOCAL? CREATE?)))))
      (IF (CADR EXP) (SET-VALUE (CADR EXP) THE-LOCALE THE-LOCALE T))
      (EVALUATE-SEQUENCE (CDDR EXP) THE-LOCALE))))
@end[TEG]

Environments are represented as objects which handle the @tc[ENV-LOOKUP]
operation.  When a
procedure created by @tc[LAMBDA] is called, @tc[BIND-VARIABLES] is
called to build up a new environment structure, one variable at a time.
This is analogous to the association-list technique used in
@cite[STEELE78ART] and @cite[MCCARTHY60], except that the environment is
represented not by list structure but by chained closure (i.e. object)
structure.  (Compare this with the code for dynamic binding in
@cite[STEELE76IMP], section 3.2.2.)

@tc[BIND-VARIABLES] is a simple recursion over the lists of formal and
actual parameters, calling @tc[BIND-VARIABLE] for each variable which
needs to be bound.  If the list of formals is an improper list then the
identifier which is its last cdr must be bound to a list of the rest of
the arguments.

@begin[TEG]
(DEFINE (BIND-VARIABLES FORMALS ACTUALS ENV)
  (COND ((PAIR? FORMALS)
         (BIND-VARIABLE (CAR FORMALS)
                        (CAR ACTUALS)
                        (BIND-VARIABLES (CDR FORMALS)
                                        (CDR ACTUALS)
                                        ENV)))
        ((NULL? FORMALS)
         ENV)
        (ELSE
         (BIND-VARIABLE FORMALS ACTUALS ENV))))

(DEFINE (BIND-VARIABLE IDENTIFIER VALUE ENV)
  (OBJECT NIL
          ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
           (COND ((EQ? ID IDENTIFIER)
                  (LOCATIVE VALUE))
                 (ELSE
                  (ENV-LOOKUP ENV ID LOCAL? CREATE?))))))
@end[TEG]

Fetching and storing the value of a variable is accomplished by
obtaining a locative to the variable using the @tc[ENV-LOOKUP]
operation, and then either examining or depositing into the locative.

@begin[TEG]
(DEFINE (VALUE ID ENV)
  (CONTENTS (ENV-LOOKUP ENV ID NIL NIL)))

(DEFINE (SET-VALUE ID ENV VAL LOCAL?)
  (SET (CONTENTS (ENV-LOOKUP ENV ID LOCAL? T)) VAL))
@end[TEG]

@tc[EVALUATE-LOCATIVE], @tc[EVALUATE-COND], @tc[EVALUATE-OR],
@tc[EVALUATE-AND], @tc[EVALUATE-CASE], and @tc[EVALUATE-LET] have been
omitted to save space; their definitions are uninteresting.  Each
could be done either as a primitive (@qu"fexpr"), as e.g. @tc[IF]
is defined above, or could be done using source-to-source
transformations (macros), using backquote and a single call to
@tc[EVALUATE].